package listnode.question;

/**
 * 题目:
      给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
      如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，
      评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
      注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改链表。

 * 两个问题:
     ①判断是否有环--->快慢指针，当相遇的时候，就有环(快指针每次两步，慢指针每次一步)
     ②找到环的入口
 * 其中会涉及到一些数学运算，但是只需要记住数学运算得出的结果:（具体的推导改成看代码随想录)
 * 即从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
 */

import listnode.ListNode;

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class DetectCycle {
    public ListNode detectCycle(ListNode head) {
        //定义两个快慢指针，来判断是否为环形链表(相当于跑圈)
        ListNode fast=head;
        ListNode slow=head;

        //只用判断快指针，因为快指针比慢的快，而且要走两步，所以也要判断next
        while(fast!=null&&fast.next!=null){//判断是否为环形
            //快指针走两步，慢指针走一步
            fast=fast.next.next;
            slow=slow.next;

            if(slow==fast){//有环形的要开始找入口
                //定义两个结点
                ListNode index1=fast;
                ListNode index2=head;

                while(index1!=index2){
                    index1=index1.next;
                    index2=index2.next;
                }
                return index1;
            }

        }
        return null;

    }
}